package basic.sort.greedy;

import java.util.*;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.greedy
 * @since JDK1.8
 */
public class SplicingStrings {

    /**
     * 暴力求解
     * @param strs 原字符串数组
     * @return 返回拼接的最小字符串
     */
    private static String violence(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        // 已经使用过的字符串的下标
        HashSet<Integer> use = new HashSet<>();
        // 全部的可能拼接字符串的集合
        List<String> all = new ArrayList<>();
        // 调用全排列函数
        fullPermutation(use, "", all, strs);

        // 最小字符串
        String lowest = all.get(0);
        // 循环比较
        for (int i = 1; i < all.size(); i++) {
            if (lowest.compareTo(all.get(i)) > 0) {
                lowest = all.get(i);
            }
        }

        return lowest;
    }

    /**
     * 全排列
     * @param use 已经使用过的字符串的下标
     * @param path 拼接的一种可能性
     * @param all 全部的可能拼接字符串的集合
     * @param strs 源字符串数组
     */
    private static void fullPermutation(
            HashSet<Integer> use,
            String path,
            List<String> all,
            String[] strs) {
        // 判断已经添加的索引大小是否已经等于字符串长度，
        // 即所有字符串已经拼接完毕没有
        if (use.size() == strs.length - 1) {
            // 拼接完毕，则集合添加这种可能性
            all.add(path);
        } else {
            // 没有则依次判断各种可能性
            for (int i = 0; i < strs.length - 1; i++) {
                // 添加一个下标，若已经添加过，则判断下一个坐标能否添加
                use.add(i);
                // 递归求解
                fullPermutation(use, path + strs[i], all, strs);
                // 移除下标是因为要知道假如01, 02, 03，这种所有可能性，
                // 只能先移除已经添加的点，才可能去尝试下一种可能性
                use.remove(i);
            }
        }
    }

    /**
     * 使用贪心算法
     *
     * @param strs 源字符串数组
     * @return 返回最小拼接字符串
     */
    private static String greedy(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        // 使用自定义比较器排序原字符串数组
        Arrays.sort(strs, new MyComparator());
        // 结果数组
        StringBuilder res = new StringBuilder();
        // 循环拼接
        for (String str : strs) {
            res.append(str);
        }

        return res.toString();
    }

    /**
     * 自定义比较器
     */
    private static class MyComparator implements Comparator<String> {
        @Override
        public int compare(String o1, String o2) {
            return (o1 + o2).compareTo(o2 + o1);
        }
    }

    /**
     * 生成随机字符串
     * @param strLen 字符串长度
     * @return 返回生成的字符串
     */
    private static String generateRandomString(int strLen) {
        char[] ans = new char[(int) (Math.random() * strLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            int value = (int) (Math.random() * 5);
            ans[i] = (Math.random() <= 0.5) ? (char) (65 + value) : (char) (97 + value);
        }
        return String.valueOf(ans);
    }

    /**
     * 生成随机的字符串数组
     * @param arrLen 数组长度
     * @param strLen 字符串长度
     * @return 返回生成的字符串数组
     */
    private static String[] generateRandomStringArray(int arrLen, int strLen) {
        String[] ans = new String[(int) (Math.random() * arrLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = generateRandomString(strLen);
        }
        return ans;
    }

    private static String[] copyStringArray(String[] arr) {
        String[] ans = new String[arr.length];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = String.valueOf(arr[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        int arrLen = 6;
        int strLen = 5;
        int testTimes = 10000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            String[] arr1 = generateRandomStringArray(arrLen, strLen);
            String[] arr2 = copyStringArray(arr1);
            if (!violence(arr1).equals(greedy(arr2))) {
                for (String str : arr1) {
                    System.out.print(str + ",");
                }
                System.out.println();
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }
}
